1. Field of the Invention
The present invention relates to a method and apparatus for motion estimation.
2. Description of the Related Art
Typically, personal computers (PC) or high-definition televisions (HDTV) perform frame rate conversion to be compatible with programs that follow various broadcasting standards such as the Phase Alternation Line (PAL) or the National Television System Committee (NTSC). Frame rate conversion (FRC) is the act of changing the number of frames per second. In particular, it is necessary to interpolate a new frame when a frame rate increases.
With recent advances in broadcasting technologies, frame rate conversion is performed after video data is compressed according to video compression standards such as Moving Picture Experts Group (MPEG) and H.263. In the field of video processing, video signals usually have redundancies due to their high autocorrelation. Data compression efficiency can be improved by removing redundancies during data compression. Here, in order to efficiently compress a video frame that changes temporally, it is necessary to remove redundancies in the time-axis direction.
Removal of redundancies in the time-axis direction is based on an idea that the amount of data to be transmitted can be greatly reduced by replacing a frame showing no movement or slight movement with a previous frame.
To this end, the act of searching for a block in a previous frame that is most similar to a block in a current frame is required, which is referred to as motion estimation (ME). A motion vector (MV) is a variable indicating how much a block has moved.
For motion estimation, a block matching algorithm (BMA) is generally used based on the accuracy of the amount of motion, a possibility of real-time processing, and hardware implementation. Generation of an intermediate image between frames for FRC uses the BMA described above and can be simply expressed as shown in FIG. 1.
Referring to FIG. 1, to interpolate an intermediate image frame Fi between a previous frame Fn-1 and a current frame Fn, a block B of the intermediate image frame Fi is generated through motion estimation between a block B of the previous frame Fn-1 and a block B of the current frame Fn.
Since the BMA is easy to implement and is suitable for real-time processing, it is used in not only FRC but also compression standards such as MPEG2/4 and H.262/264. Although the BMA exhibits superior performance in horizontal and/or vertical motion estimation, its performance is poor in rotation or enlargement/reduction of an image.
To improve the accuracy of motion estimation in the use of the BMA, the size of a matching block should be increased. The increase in a block size not only improves accuracy, but also increases the amount of computation and makes precise representation difficult. On the other hand, a decrease in a block size not only reduces the amount of computation and makes precise representation possible, but also degrades accuracy.
Among conventional techniques for improving matching accuracy and allowing precise representation, there is a technique for motion estimation using a block having a guard block. In the technique, an M×M block is used for motion estimation and an N×N block is used for motion compensation as shown in FIG. 2A.
Referring to FIG. 2B, motion estimation is performed using an M×M block having a guard block, and the actual motion compensation is performed using an N×N motion compensation block. Thus, matching accuracy is improved and representation precision can be improved through interpolation using an N×N block. However, such a technique still increases the amount of computation.